
\documentclass{article}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{fancyhdr}

\setcounter{MaxMatrixCols}{10}
%TCIDATA{OutputFilter=LATEX.DLL}
%TCIDATA{Version=5.00.0.2552}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{Created=Fri Nov 24 20:35:23 2000}
%TCIDATA{LastRevised=Tuesday, February 21, 2017 22:08:05}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="DocumentShell" CONTENT="General\Blank Document">}
%TCIDATA{CSTFile=LaTeX article (bright).cst}

\def \go{\char"AB ~\ignorespaces}
\newtheorem{theorem}{Theorem}
\newtheorem{acknowledgement}[theorem]{Acknowledgement}
\newtheorem{algorithm}[theorem]{Algorithm}
\newtheorem{axiom}[theorem]{Axiom}
\newtheorem{case}[theorem]{Case}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{conclusion}[theorem]{Conclusion}
\newtheorem{condition}[theorem]{Condition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{criterion}[theorem]{Criterion}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{solution}[theorem]{Solution}
\newtheorem{summary}[theorem]{Summary}
\newenvironment{proof}[1][Proof]{\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\setlength{\headsep}{5mm}
\setlength{\topmargin}{-15mm}
\setlength{\oddsidemargin}{-10mm}
\setlength{\textwidth}{190mm}
\setlength{\textheight}{245mm}
\newcommand{\trans}[1]{\hbox{$\hspace{0.2em}^t\hspace{-0.2em}#1$}}
\pagestyle{fancy}
\lhead{ EXERCICES MPSI}\chead{ \LARGE {A 5.  ARITHMÉTIQUE}} \rhead {R. FERRÉOL  16/17}
\input{tcilatex}

\begin{document}


\fbox{I \textbf{SYST\`{E}MES DE NUM\'{E}RATION, DIVISIBILIT\'{E}.}}

\begin{enumerate}
\item : Les "repunits", ou unit\'{e}s r\'{e}p\'{e}t\'{e}es.

\begin{enumerate}
\item Montrer qu'un nombre form\'{e} de 2 goupes identiques de 3 chiffres
(comme 127127) est toujours divisible par 7, par 11 et par 13 ; et pour 2
groupes de 4 chiffres, ou 3 groupes de 2 chiffres ?

\item Montrer que plus g\'{e}n\'{e}ralement, dans n'importe quel base, un
nombre form\'{e} d'un motif diff\'{e}rent de 1 r\'{e}p\'{e}t\'{e} au moins
deux fois n'est jamais premier. En d\'{e}duire que si $n$ n'est pas premier,
le nombre $R_{n}$ qui s'\'{e}crit $\overset{n\text{ fois}}{\overbrace{%
\overline{11...11}}}$ en base $b$ n'est pas premier, quelle que soit la
base. Que retrouve-t-on lorsque $b=2$ ?

\item Montrer que que $R_{n}$ en base 10 ne peut \^{e}tre un carr\'{e}
(utiliser des congruences modulo 4).
\end{enumerate}

\item : Montrer qu'en base $b,$ le nombre $0,a_{1}a_{2}...a_{n}\underbrace{%
a_{1}a_{2}...a_{n}}...$ est \'{e}gal \`{a} $\dfrac{\overline{%
a_{1}a_{2}...a_{n}}}{b^{n}-1}.$ Que vaut par exemple 0,9999... en base 10 ?

\item : Trouver $a$ et $b$ entiers naturels tels que $\dfrac{a+b}{2}=%
\overline{xy}$ et $\sqrt{ab}=\overline{yx}$ avec $x\neq y$ (en base $10$).

\item :

\begin{enumerate}
\item D\'{e}terminer les r\'{e}sidus sym\'{e}triques (i.e. compris entre $-3$
et 3) modulo 7 de 1, 10, 10$^{2},$ 10$^{3},$ etc ; en d\'{e}duire un crit%
\`{e}re de divisibilit\'{e} par 7 en base 10.

\item Faire de m\^{e}me pour 13.\newline
R\'{e}ponses : 
\begin{eqnarray*}
N &\equiv
&a_{0}+3a_{1}+2a_{2}-a_{3}-3a_{4}-2a_{5}+a_{6}+3a_{7}+2a_{8}-a_{9}...\,\,\,%
\,[7]\newline
\\
N &\equiv &a_{0}-3a_{1}-4a_{2}-a_{3}+3a_{4}+4a_{5}+a_{6}...\,\,\,\,[13]
\end{eqnarray*}
\end{enumerate}

\begin{enumerate}
\item Trouver un crit\`{e}re de divisibilit\'{e} par $7$ en base $20.$

\item Trouver un crit\`{e}re de divisibilit\'{e} par $13$ en base $40.$
\end{enumerate}

\item Autre crit\`{e}re de divisibilit\'{e} par 7.

Montrer que si pour $N=\overline{a_{n}a_{n-1}...a_{0}}$ , on pose $%
b_{0}=a_{n}$ et $b_{k}=3b_{k-1}+a_{n-k}$ pour $k=1..n$, alors $N\equiv
b_{n}\;\;\left[ 7\right] $ ; appliquer \`{a} $2012$ et \`{a} $12345.$

\item Encore un autre.

\begin{enumerate}
\item Montrer qu'un nombre \'{e}crit en base 10 est divisible par 7 ssi en
retranchant le double de son dernier chiffre au nombre constitu\'{e} des
autres chiffres, on obtient un nombre divisible par 7 ; appliquer ce crit%
\`{e}re \`{a} $2015$ et \`{a} $12345.$

\item * Montrer que plus g\'{e}n\'{e}ralement si pour $N=\overline{%
a_{n}a_{n-1}...a_{0}}$ , on pose $b_{0}=a_{0}$ et $b_{k}=-2b_{k-1}+a_{k}$
pour $k=1..n$, alors $N\equiv 10^{n}b_{n}\;\;\left[ 7\right] .$

\item * En remarquant que $40=3\times 13+1$ et $50=3\times 17-1$ $,$ trouver
de m\^{e}me un crit\`{e}re de divisibilit\'{e} par $13$ et un crit\`{e}re de
divisibilit\'{e} par $17$ en base 10 ; les appliquer \`{a} $2015$ et \`{a} $%
12345,$ et trouver deux relations similaires \`{a} celle de (b).
\end{enumerate}

\item * : D\'{e}montrer que dans une base donn\'{e}e, il n'y a qu'un nombre
fini de nombres \'{e}gaux \`{a} la somme des cubes de leurs chiffres ; D\'{e}%
terminer ces nombres en base 5 et 10.

\item : Montrer que, pour tout $n$ entier :

\begin{enumerate}
\item $n^{3}-n$ est multiple de 6, et que si $n$ est impair, $n^{3}-n$ est m%
\^{e}me multiple de 24.

\item si $n$ n'est ni pair ni multiple de 3, le reste de la division par 24
de $n^{2}$ est 1.

\item $n^{5}-5n^{3}+4n$ est multiple de 120.

\item $n\left( n^{2}-1\right) \left( 4n^{2}-1\right) \left( 9n^{2}-1\right) $
est multiple de 210.
\end{enumerate}

\item * : D\'{e}montrer que parmi $n$ entiers pris au hasard, on peut
toujours en trouver un certain nombre dont la somme est divisible par $n.$

\item Montrer \`{a} l'aide de congruences, que :

\begin{enumerate}
\item $\forall n\in \mathbb{N}^{\ast }\quad 11\left\vert \left(
2^{6n-5}+3^{2n}\right) \right. $ et $17\left\vert \left( 3\times
5^{2n-1}+2^{3n-2}\right) \right. .$

\item $\forall n\in \mathbb{N}\quad n^{2}\left\vert \left( \left( n+2\right)
^{n+2}-2^{n+2}\left( n+1\right) ^{n+1}\right) \right. .$
\end{enumerate}

\item : D\'{e}montrer que les entiers congrus \`{a} $-1$ modulo $4$ ne
peuvent pas s'\'{e}crire comme somme de deux carr\'{e}s et que les entiers
congrus \`{a} $-1$ modulo $8$ ne peuvent pas s'\'{e}crire comme somme de 
\textit{trois} carr\'{e}s (par contre, il a \'{e}t\'{e} d\'{e}montr\'{e} que
tout entier peut s'\'{e}crire comme somme de 4 carr\'{e}s).\newline

\item * : Les entiers entre 1 et $n$ ont en moyenne environ $\ln n$
diviseurs, \`{a} un pr\`{e}s pr\`{e}s (ou plus pr\'{e}cis\'{e}ment, la
moyenne du nombre de diviseurs des entiers de 1 \`{a} $n$ est comprise entre 
$\ln n-1$ et $\ln n+1$)

\begin{enumerate}
\item V\'{e}rifier cette propri\'{e}t\'{e} pour $n=10.$

Pour deux entiers naturels $i$ et $j$ on pose $\delta \left( i,j\right) =1$
si $i$ divise $j,$ et 0 sinon.

\item Pour un entier naturel $n$, que repr\'{e}sente le nombre $d\left(
n\right) =\underset{i=1}{\overset{n}{\dsum }}\delta \left( i,n\right) $ ?

\item Montrer que $\underset{j=i}{\overset{n}{\dsum }}\delta \left(
i,j\right) =\left\lfloor \dfrac{n}{i}\right\rfloor .$

\item En d\'{e}duire que $S\left( n\right) =\underset{j=1}{\overset{n}{\dsum 
}}d\left( j\right) $ est compris entre $n\left( h_{n}-1\right) $ et $nh_{n}$
o\`{u} $h_{n}=\underset{i=1}{\overset{n}{\dsum }}\dfrac{1}{i}.$

\item En utilisant l'encadrement $\ln n\leqslant h_{n}\leqslant \ln n+1,$
montrer $\dfrac{S\left( n\right) }{n}\simeq \ln n\pm 1$.
\end{enumerate}

\fbox{II \textbf{TH\'{E}OR\`{E}MES DE GAUSS ET DE B\'{E}ZOUT}}\newline
\newline

\item : Montrer que si un r\'{e}el $x$ est tel que $ax$ et $bx$ sont
entiers, avec $a$ et $b$ entiers premiers entre eux, alors $x$ est entier.

\item * : En utilisant la relation $p\left( 
\begin{array}{c}
n \\ 
p%
\end{array}%
\right) =n\left( 
\begin{array}{c}
n-1 \\ 
p-1%
\end{array}%
\right) ,$ montrer que pour $1\leqslant p\leqslant n$ , $\left( 
\begin{array}{c}
n \\ 
p%
\end{array}%
\right) $ est divisible par $\dfrac{n}{\func{pgcd}\left( n,p\right) }$ et
par $\dfrac{p+1}{\func{pgcd}(n+1,p+1)}$ ; en d\'{e}duire que $\left( 
\begin{array}{c}
2n \\ 
n%
\end{array}%
\right) $ est pair et divisible par $n+1.$

\item : Montrer que si $z$ est une racine $n^{i\grave{e}me}$ et $m^{i\grave{e%
}me}$ de l'unit\'{e}, alors $z$ est une racine $d^{i\grave{e}me}$ de l'unit%
\'{e} avec $d=\func{pgcd}\left( n,m\right) .$

\item * : On dit qu'une suite $(u_{n})$ est $p$-p\'{e}riodique si $%
u_{n}=u_{n+p}$ pour tout $n\in \mathbb{N}$ ($p$ entier \TEXTsymbol{>} 0).

\begin{enumerate}
\item Montrer que si $(u_{n})$ est \`{a} la fois $p$-p\'{e}riodique et $q$-p%
\'{e}riodique alors $(u_{n})$ est $d$-p\'{e}riodique avec $d=\func{pgcd}%
(p,q).$

\item En d\'{e}duire que si $p$ est la plus petite p\'{e}riode $\geqslant 1$
de $(u_{n})$ et si $q$ est une autre p\'{e}riode alors $p$ divise $q.$

\item On suppose que $(u_{n})$ est r\'{e}currente simple ($u_{n}=f(u_{n-1}))$
; montrer que si $u_{p}=u_{0}$ alors $(u_{n})$ est $p$-p\'{e}riodique.
\end{enumerate}

\item * : Soient $a$ et $b$ deux entiers $>0$.

\begin{enumerate}
\item Montrer que si $a$ et $b$ sont premiers entre eux, il existe un unique
couple d'entiers $\geqslant $ $0$ $(u,v)$ tel que $au-bv=1$ v\'{e}rifiant $%
u<b$ et $v<a.$

\item En d\'{e}duire que si $a$ et $b$ sont premiers entre eux, $a\mathbb{N}%
-b\mathbb{N}=\mathbb{Z}.$

\item Montrer que $a$ et $b$ sont \textit{non} premiers entre eux si et
seulement s'il existe deux entiers $>0$ $u$ et $v$ tels que $au=bv,$ avec $%
u<b$ et $v<a.$
\end{enumerate}

\item :

\begin{enumerate}
\item Soient $a,a^{\prime }$ et $b$ trois entiers ; on dit que $a^{\prime }$
est inverse de $a$ modulo $b$ si et seulement si $aa^{\prime }\equiv
1\;\;[b] $ ; montrer que $a$ poss\`{e}de un inverse modulo $b$ si et
seulement si $a$ et $b$ sont premiers entre eux.

\item Soit $p$ un nombre premier ; quels sont les entiers ayant un inverse
modulo $p$ ? Pour $p$ impair, d\'{e}terminer un inverse de 1, de $-1$, de 2
modulo $p$.

\fbox{III \textbf{NOMBRES PREMIERS ET D\'{E}COMPOSITION EN PRODUITS DE
FACTEURS PREMIERS}}
\end{enumerate}

\item : L'\^{a}ge du capitaine.\newline
La pertuisane est une sorte de lance utilis\'{e}e au XV$^{\grave{e}me}$ et
XVI$^{\grave{e}me}$ si\`{e}cles. Voici le probl\`{e}me : le dernier jour
d'un certain mois de la Premi\`{e}re Guerre Mondiale, un obus \'{e}clate et
met au jour le squelette d'un capitaine. En multipliant l'\^{a}ge du
capitaine au moment de sa mort par le quart du nombre d'ann\'{e}es \'{e}coul%
\'{e}es entre sa mort et la date d'\'{e}clatement de l'obus, par le num\'{e}%
ro du jour remarquable du mois d'\'{e}clatement de l'obus, et par la
longueur exprim\'{e}e en pieds de la pertuisane trouv\'{e}e \`{a} c\^{o}t%
\'{e} du squelette, on trouve : $471\,569.$\newline
Quel est l'\^{a}ge du capitaine, et quelle est la date de la bataille ?

\item :

\begin{enumerate}
\item Montrer que si un carr\'{e} $a^{2}$ divise un carr\'{e} $b^{2}$ alors $%
a$ divise $b$ et $\dfrac{b^{2}}{a^{2}}$ est un carr\'{e}.

\item En d\'{e}duire que si $n$ est un entier naturel non carr\'{e} alors $%
\sqrt{n}\notin \mathbb{Q}.$

\item G\'{e}n\'{e}raliser (a) et (b) en rempla\c{c}ant 2 par $q$ entier $%
\geqslant 2.$

\item * La g\'{e}n\'{e}ralisation compl\`{e}te.

Montrer que si $n$ et $m$ sont deux entiers $>0$ premiers entre eux, $r$ est
un rationnel $>0$ qui n'est pas la puissance $n$-i\`{e}me d'un rationnel,
alors $\sqrt[n]{r^{m}}$ n'est pas rationnel.
\end{enumerate}

\item :

\begin{enumerate}
\item Montrer l'unicit\'{e} de la forme irr\'{e}ductible d'une fraction ;
c'est-\`{a}-dire que si $\dfrac{a}{b}=\dfrac{c}{d}$ avec $a,b,c,d\in \mathbb{%
N}^{\ast },$ $a$ et $b$ premiers entre eux, $c$ et $d$ premiers entre eux,
alors $a=c$ et $b=d.$

\item En d\'{e}duire que si $a,b\in \mathbb{N}^{\ast }$ avec $a$ et $b$
premiers entre eux, $a$ ou $b$ non carr\'{e}, alors $\sqrt{\dfrac{a}{b}}%
\notin \mathbb{Q}$ ; g\'{e}n\'{e}raliser \`{a} $\sqrt[n]{\dfrac{a}{b}}.$
\end{enumerate}

\item Petit th\'{e}or\`{e}me de Fermat.

\begin{enumerate}
\item Montrer que si $p$ est premier et $k$ est un entier entre $1$ et $p-1$
alors $\left( 
\begin{array}{c}
p \\ 
k%
\end{array}%
\right) $ est multiple de $p$.

\item En d\'{e}duire que pour tout naturel $n,$ $n^{p}\equiv n\ \ \ \left[ p%
\right] .$
\end{enumerate}

\item Autre application du 22 a).

Soit $\left( f_{n}\right) $ une suite d'entiers du type fibonaccien v\'{e}%
rifiant pour tout naturel $n$ : $f_{n+2}=f_{n+1}+f_{n}.$

\begin{enumerate}
\item Montrer pour tous naturels $n$ et $p$ :%
\begin{equation*}
f_{n+2p}=\underset{k=0}{\overset{p}{\dsum }}\left( 
\begin{array}{c}
p \\ 
k%
\end{array}%
\right) f_{n+k}
\end{equation*}

\item En d\'{e}duire que si $p$ est premier, $f_{n+2p}-f_{n+p}-f_{n}$ est
multiple de $p$ pour tout naturel $n.$
\end{enumerate}

\item Encore une autre application.

Soit $\left( L_{n}\right) $ la suite dite de Lucas d\'{e}finie par $%
L_{0}=2,L_{1}=1$ et pour tout naturel $n$ : $L_{n+2}=L_{n+1}+L_{n}.$

\begin{enumerate}
\item Montrer que $L_{n}=\left( \dfrac{1+\sqrt{5}}{2}\right) ^{n}+\left( 
\dfrac{1-\sqrt{5}}{2}\right) ^{n}.$

\item D\'{e}duire de a) et de 22 a) que si $p$ est premier, alors $%
2^{p}L_{p}=2+2pa$ o\`{u} $a$ est un entier.

\item En d\'{e}duire que $L_{p}\equiv 1$ $[p].$
\end{enumerate}

\item On pose $P_{n}(x)=\left( x+1\right) \left( x^{2}+1\right) \left(
x^{4}+1\right) \cdots \left( x^{2^{n}}+1\right) $ $;$\newline

\begin{enumerate}
\item Simplifier $\left( x-1\right) P_{n}\left( x\right) .$

\item En d\'{e}duire la forme d\'{e}velopp\'{e}e de $P_{n}\left( x\right) .$

\item En d\'{e}duire que si $F_{n}=2^{2^{n}}+1\,;%
\,F_{n}=F_{0}F_{1}...F_{n-1}+2$ ; o\`{u} $F_{n}$ est le $n$i\`{e}me nombre
de Fermat.

\item En d\'{e}duire que si, contrairement \`{a} ce qu'esp\'{e}rait Fermat,
les nombres de Fermat ne sont pas tous premiers, ils sont au moins premiers
deux \`{a} deux.

\item En d\'{e}duire une autre d\'{e}monstration du fait qu'il y a un nombre
infini de nombres premiers.
\end{enumerate}

\item :

\begin{enumerate}
\item Montrer que les $\left( n-1\right) $ entiers $n!+2,\;n!+3,\;...,\;n!+n$
pour $n\geqslant 3$ sont tous compos\'{e}s ; en d\'{e}duire qu'on peut
trouver des listes d'entiers compos\'{e}s cons\'{e}cutifs aussi longues
qu'on veut.

\item On pose $n\#\overset{def}{=}\underset{%
\begin{array}{c}
2\leqslant p\leqslant n \\ 
p\text{ premier}%
\end{array}%
}{\prod }p$ (\textit{primorielle} de $n)$ ; montrer que de nouveau les $%
\left( n-1\right) $ entiers $n\#+2,\;n\#+3,\;...,\;n\#+n$ sont tous compos%
\'{e}s.
\end{enumerate}

\item * :

\begin{enumerate}
\item En s'inspirant de la d\'{e}monstration d'Euclide de l'infinit\'{e} des
nombres premiers, montrer qu'il existe une infinit\'{e} de nombres premiers
congrus \`{a} $-1$ modulo $4$ (indication : $N=4p_{1}p_{2}...p_{n}+1).$

\item Montrer de m\^{e}me qu'il existe une infinit\'{e} de nombres premiers
congrus \`{a} $-1$ modulo $6.$

REM : le th\'{e}or\`{e}me de Dirichlet, bien plus difficile \`{a} d\'{e}%
montrer, affirme que dans toute suite arithm\'{e}tique dont la raison est
premi\`{e}re avec le premier terme, il existe une infinit\'{e} de nombres
premiers.
\end{enumerate}

\item *: Pour $x\in \mathbb{N}^{\ast },$ $\mathcal{D}_{x}$ d\'{e}signe
l'ensemble des diviseurs de $x$ dans $\mathbb{N}.$ Consid\'{e}rons pour $%
a,b\in \mathbb{N}^{\ast }$ l'application $\varphi :\left\vert 
\begin{array}{c}
\mathcal{D}_{a}\times \mathcal{D}_{b}\rightarrow \mathcal{D}_{ab} \\ 
\left( d,d^{\prime }\right) \mapsto dd^{\prime }%
\end{array}%
\right. $

\begin{enumerate}
\item A quelle condition n\'{e}cessaire et suffisante $\varphi $ est-elle
injective ?

\item A quelle condition n\'{e}cessaire et suffisante $\varphi $ est-elle
surjective ?
\end{enumerate}

\item : Soit $\;n=\underset{k=1}{\overset{m}{\prod }}p_{k}^{\alpha _{k}}$ un
naturel d\'{e}compos\'{e} en produit de facteurs premiers.

\begin{enumerate}
\item Montrer que le nombre de diviseurs de $n$ est $N=\underset{k=1}{%
\overset{m}{\prod }}\left( \alpha _{k}+1\right) .$

\item Que dire donc d'un entier naturel non nul ayant un nombre impair de
diviseurs ?

\item Montrer que la somme des diviseurs de $n$ est $S=\underset{k=1}{%
\overset{m}{\prod }}\dfrac{p_{k}^{\alpha _{k}+1}-1}{p_{k}-1}.$

\item * Montrer que le produit des diviseurs de $n$ est $P=n^{\frac{N}{2}}$.

\item * Sans faire intervenir la d\'{e}composition en produit de facteurs
premiers, mais en utilisant la propri\'{e}t\'{e} d'Eratosth\`{e}ne, et en s%
\'{e}parant les cas : $n$ carr\'{e} ou non, montrer que :

\begin{enumerate}
\item $2\leqslant N\leqslant 2\sqrt{n}.$

\item $n+1\leqslant S\leqslant (n+1)\sqrt{n}$

\item $P=\sqrt{n}^{N}.$

\item La somme des inverses des diviseurs de $n$ est $\dfrac{S}{n}.$
\end{enumerate}
\end{enumerate}

\item : Nombres parfaits.

\begin{enumerate}
\item Soit $M_{p}=2^{p}-1$ un nombre de Mersenne premier. Montrer que $%
N=2^{p-1}M_{p}$ est un nombre \textquotedblright parfait\textquotedblright ,
c'est-\`{a}-dire que la somme de ses diviseurs \textbf{stricts }(i.e. sauf
lui-m\^{e}me) est \'{e}gale \`{a} lui-m\^{e}me.

\item ** D\'{e}montrer que tout nombre parfait pair est du type pr\'{e}c\'{e}%
dent.
\end{enumerate}

\item : Nombres amiables, formule de Th\={a}bit ibn Qurra (850).

Soit $p=3.2^{n-1}-1,q=3.2^{n}-1,r=9.2^{2n-1}-1$ pour un entier $n\geqslant 1$
; montrer que si $p,q,r$ sont premiers, alors $a=2^{n}pq$ et $b=2^{n}r$
forment une paire de nombres "amiables", ce qui signifie que la somme des
diviseurs stricts de l'un est \'{e}gale \`{a} l'autre.

Donner un exemple.

\item * : Par combien de z\'{e}ros se termine $100!$ ?\newline
Soient $n\in \mathbb{N}^{\ast }\backslash \left\{ 1\right\} \;;\;p\in 
\mathbb{P\;};\alpha _{p}=v_{p}\left( n!\right) $ l'exposant de $p$ dans la d%
\'{e}composition de $n!$ en produit de facteurs premiers.

\begin{enumerate}
\item Que vaut $\alpha _{p}$ pour $p>n$ ?

\item Pour $p\leqslant n$ on note $n_{1}$ le quotient de la division de $n$
par $p.$ Montrer que 
\begin{equation*}
\alpha _{p}=n_{1}+\alpha _{p}\left( n_{1}!\right)
\end{equation*}%
En d\'{e}duire un algorithme pour calculer $\alpha _{p}.$

\item Calculer $\alpha _{2}\left( 100!\right) $ et $\alpha _{5}\left(
100!\right) $ et conclure quant au nombre de z\'{e}ros terminant $100!$.
\end{enumerate}

\item : D\'{e}montrer qu'un polyn\^{o}me non constant \`{a} coefficients
entiers $P=\overset{n}{\underset{k=0}{\dsum }}a_{k}X^{k}$ ne peut pas
prendre \textit{uniquement} des valeurs premi\`{e}res pour les valeurs enti%
\`{e}res naturelles de la variable, mais que par contre, il est possible
qu'il en prenne une infinit\'{e}.

\item : Des nombres premiers en progression arithm\'{e}tique.

\begin{enumerate}
\item Montrer que si 3 entiers non multiples de 3 sont en progression arithm%
\'{e}tique, la raison est multiple de 3.

\item * Soit $p$ un nombre premier ; on rappelle que si $p$ divise un
produit, il en divise l'un des termes.\newline
Montrer que si $p$ entiers non multiples de $p$ sont en progression arithm%
\'{e}tique, la raison est multiple de $p.$\newline
Indication : soit $x_{k}$ le reste dans la division par $p$ de $a+kr$ ;
montrer que les nombres $x_{0},x_{1},$...$,x_{p-1}$ sont $p$ nombres compris
entre 1 et $p-1...$\newline
Montrer que ceci est faux si $p$ n'est plus suppos\'{e} premier.

\item * Application : montrer que si 3 nombres premiers $\neq $ 3 sont en
progression arithm\'{e}tique, la raison est multiple de 6 ; donner un
exemple.

\item * De m\^{e}me, montrer que si 5 nombres premiers $\neq $ 5 sont en
progression arithm\'{e}tique, la raison est multiple de 30 ; donner un
exemple.
\end{enumerate}

\item * : D\'{e}signons par $\pi (n)$ le nombre de nombres premiers $%
\leqslant n.$ Il\ a \'{e}t\'{e} d\'{e}montr\'{e} que pour $n\geqslant 11$ : 
\begin{equation*}
\dfrac{n}{\ln n}\leqslant \pi (n)\leqslant 1,3\dfrac{n}{\ln n}
\end{equation*}

\begin{enumerate}
\item V\'{e}rifier num\'{e}riquement cette in\'{e}galit\'{e} en calculant $%
\dfrac{\pi (n)}{\dfrac{n}{\ln n}}$ pour $11\leqslant n\leqslant 100$ (calcul
formel).

\item D\'{e}duire de cette in\'{e}galit\'{e} le fait qu'il existe toujours
au moins un nombre premier entre $n$ et $2n$ (r\'{e}sultat appel\'{e} le
\textquotedblright postulat de Bertrand\textquotedblright ).\newline
Rem : il a \'{e}t\'{e} \'{e}galement d\'{e}montr\'{e} que $\pi (n)\sim 
\dfrac{n}{\ln n}$ (Th\'{e}or\`{e}me de Hadamard et de la Vall\'{e}e Poussin).

REP\ : pour $n\geqslant 11,\ \pi \left( 2n\right) >\pi \left( n\right) $ d%
\`{e}s que $\dfrac{2n}{\ln 2n}>1,3\dfrac{n}{\ln n}$ soit $2\ln n>1,3\left(
\ln n+\ln 2\right) ,$ soit $n>2^{13/7}$ soit $n\geqslant 4,$ ce qui est bien
le cas.
\end{enumerate}

\item *: Obtention d'un minorant de $\pi (n),$ l\'{e}g\`{e}rement moins bon
que le $\dfrac{n}{\ln n}$ de l'exercice pr\'{e}c\'{e}dent, mais d\'{e}montr%
\'{e} (preuve de Tchebychev).

\begin{enumerate}
\item On note  $m_{n}=$ ppcm $(1,2,...,n)$, et $\alpha $ l'exposant du
nombre premier $p$ dans la d\'{e}composition en produit de facteurs premiers
de $m_{n}.$

\begin{enumerate}
\item Montrer que $p^{\alpha }\leqslant n<p^{\alpha +1}.$

\item En d\'{e}duire que $m_{n}=\underset{p\text{ premier }\leqslant n}{%
\dprod }p^{\left\lfloor \dfrac{\ln n}{\ln p}\right\rfloor }$

\item En d\'{e}duire que $\pi \left( n\right) \geqslant \dfrac{\ln m_{n}}{%
\ln n};$ on va maintenant obtenir un minorant de $m_{n}.$
\end{enumerate}

\item Consid\'{e}rons $I_{n}=\dint\limits_{0}^{1}t^{n}\left( 1-t\right)
^{n}dt,$ pour $n\geqslant 0$ .

\begin{enumerate}
\item Montrer que $I_{n}=\underset{k=0}{\overset{n}{\dsum }}\dfrac{\left(
-1\right) ^{k}\left( 
\begin{array}{c}
n \\ 
k%
\end{array}%
\right) }{n+k+1};$

\item En d\'{e}duire que$\dfrac{1}{m_{2n+1}}\leqslant I_{n}.$

\item Montrer que $I_{n}\leqslant \dfrac{1}{4^{n}}.$

\item Montrer que pour $n\geqslant 2,$ $m_{n}\geqslant 2^{n-2}.$
\end{enumerate}

\item Montrer l'in\'{e}galit\'{e} annonc\'{e}e : $\pi \left( n\right)
\geqslant \ln 2\dfrac{n-2}{\ln n}$ .
\end{enumerate}

\item * : Majoration de $n\#$ (\textit{primorielle} de $n).$

Dans cet exercice, $n$ d\'{e}signe toujours un entier $\geqslant 2$ fix\'{e}%
, $q$ la partie enti\`{e}re sup\'{e}rieure de $n/2$ et $p$ un nombre \textit{%
premier}.

\begin{enumerate}
\item Montrer que $\underset{q\leqslant p\leqslant n}{\prod }p$ divise $%
\left( 
\begin{array}{c}
n \\ 
q%
\end{array}%
\right) $; en d\'{e}duire que $\underset{q\leqslant p\leqslant n}{\prod }%
p\leqslant 2^{n}.$

\item En d\'{e}duire par r\'{e}currence forte que $n\#\overset{def}{=}%
\underset{2\leqslant p\leqslant n}{\prod }p\leqslant 4^{n}$ (d\'{e}%
monstration d\^{u}e \`{a} Paul Erd\"{o}s, 1932). On peut d\'{e}montrer qu'en
fait $n\#=e^{n+o\left( n\right) }.$
\end{enumerate}
\end{enumerate}

\end{document}
